1. Field of the Invention
This invention relates generally to autonomous vehicles or robots, and more specifically to methods and mobile robotic devices for covering a specific area as might be required of, or used as, robotic cleaners or lawn mowers.
2. Description of Prior Art
For purposes of this description, examples will focus on the problems faced in the prior art as related to robotic cleaning (e.g., dusting, buffing, sweeping, scrubbing, dry mopping or vacuuming). The claimed invention, however, is limited only by the claims themselves, and one of skill in the art will recognize the myriad of uses for the present invention beyond indoor, domestic cleaning.
Robotic engineers have long worked on developing an effective method of autonomous cleaning. By way of introduction, the performance of cleaning robots should concentrate on three measures of success: coverage, cleaning rate and perceived effectiveness. Coverage is the percentage of the available space visited by the robot during a fixed cleaning time, and ideally, a robot cleaner would provide 100 percent coverage given an infinite run time. Unfortunately, designs in the prior art often leave portions of the area uncovered regardless of the amount of time the device is allowed to complete its tasks. Failure to achieve complete coverage can result from mechanical limitations—e.g., the size and shape of the robot may prevent it from reaching certain areas—or the robot may become trapped, unable to vary its control to escape. Failure to achieve complete coverage can also result from an inadequate coverage algorithm. The coverage algorithm is the set of instructions used by the robot to control its movement. For the purposes of the present invention coverage is discussed as a percentage of the available area visited by the robot during a finite cleaning time. Due to mechanical and/or algorithmic limitations, certain areas within the available space may be systematically neglected. Such systematic neglect is a significant limitation in the prior art.
A second measure of a cleaning robot's performance is the cleaning rate given in units of area cleaned per unit time. Cleaning rate refers to the rate at which the area of cleaned floor increases; coverage rate refers to the rate at which the robot covers the floor regardless of whether the floor was previously clean or dirty. If the velocity of the robot is v and the width of the robot's cleaning mechanism (also called work width) is w then the robots coverage rate is simply wv, but its cleaning rate may be drastically lower.
A robot that moves in a purely randomly fashion in a closed environment has a cleaning rate that decreases relative to the robot's coverage rate as a function of time. This is because the longer the robot operates the more likely it is to revisit already cleaned areas. The optimal design has a cleaning rate equivalent to the coverage rate, thus minimizing unnecessary repeated cleanings of the same spot. In other words, the ratio of cleaning rate to coverage rate is a measure of efficiency and an optimal cleaning rate would mean coverage of the greatest percentage of the designated area with the in minimum number of cumulative or redundant passes over an area already cleaned.
A third metric cleaning robot performance is the perceived effectiveness of the robot. This measure is ignored in the prior art. Deliberate movement and certain patterned movement is favored as users will perceive a robot that contains deliberate movement as more effective.
While coverage, cleaning rate and perceived effectiveness are the performance criteria discussed herein, a preferred embodiment of the present invention also takes into account the ease of use in rooms of a variety of shapes and sizes (containing a variety of unknown obstacles) and the cost of the robotic components. Other design criteria may also influence the design, for example the need for collision avoidance and appropriate response to other hazards.
As described in detail in Jones, Flynn & Seiger, Mobile Robots: Inspiration to Implementation second edition, 1999, A K Peters, Ltd., and elsewhere, numerous attempts have been made to build vacuuming and cleaning robots. Each of these robots has faced a similar challenge: how to efficiently cover the designated area given limited energy reserves.
We refer to maximally efficient cleaning, where the cleaning rate equals the coverage rate, as deterministic cleaning. As shown in FIG. 1A, a robot 1 following a deterministic path moves in such a way as to completely cover the area 2 while avoiding all redundant cleaning. Deterministic cleaning requires that the robot know both where it is and where it has been; this in turn requires a positioning system. Such a positioning system—a positioning system suitably accurate to enable deterministic cleaning might rely on scanning laser rangers, ultrasonic transducers, carrier phase differential GPS, or other methods—can be prohibitively expensive and involve user set-up specific to the particular room geometries. Also, methods that rely on global positioning are typically incapacitated by the failure of any part of the positioning system.
One example of using highly sophisticated (and expensive) sensor technologies to create deterministic cleaning is the RoboScrub device built by Denning Mobile Robotics and Windsor Industries, which used sonar, infrared detectors, bump sensors and high-precision laser navigation. RoboScrub's navigation system required attaching large bar code targets at various positions in the room. The requirement that RoboScrub be able to see at least four targets simultaneously was a significant operational problem. RoboScrub, therefore, was limited to cleaning large open areas.
Another example, RoboKent, a robot built by the Kent Corporation, follows a global positioning strategy similar to RobotScrub. RoboKent dispenses with RobotScrub's more expensive laser positioning system but having done so RoboKent must restrict itself only to areas with a simple rectangular geometry, e.g., long hallways. In these more constrained regions, position correction by sonar ranging measurements is sufficient. Other deterministic cleaning systems are described, for example, in U.S. Pat. No. 4,119,900 (Kremnitz) U.S. Pat. No. 4,700,427 (Knepper) U.S. Pat. No. 5,353,224 (Lee et al.), U.S. Pat. No. 5,537,017 (Feiten et al.), U.S. Pat. No. 5,548,511 (Bancroft), U.S. Pat. No. 5,650,702 (Azumi).
Because of the limitations and difficulties of deterministic cleaning some robots have relied on pseudo-deterministic schemes. One method of providing pseudo-deterministic cleaning is an autonomous navigation method known as dead reckoning. Dead reckoning consists of measuring the precise rotation of each robot drive wheel (using for example optical shaft encoders). The robot can then calculate its expected position in the environment given a known starting point and orientation. One problem with this technique is wheel slippage. If slippage occurs, the encoder on that wheel registers a wheel rotation even though that wheel is not driving the robot relative to the ground. As shown in FIG. 1B, as the robot 1 navigates about the room these drive wheel slippage errors accumulate making this type of system unreliable for runs of any substantial duration. (The path no longer consists of tightly packed rows, as compared to the deterministic coverage shown in FIG. 1A.) The result of reliance on dead reckoning is intractable systematic neglect; in other words, areas of the floor are not cleaned.
One example of a pseudo-deterministic a system is the Cye robot from Probotics, Inc. Cye depends exclusively on dead reckoning and therefore takes heroic measures to maximize the performance of its dead reckoning system. Cye must begin at a user-installed physical registration spot in a known location where the robot fixes its position and orientation. Cye then keeps track of position as it moves away from that spot. As Cye moves, uncertainty in its position and orientation increase. Cye must make certain to return to a calibration spot before this error grows so large that it will be unlikely to locate a calibration spot. If a calibration spot is moved or blocked or if excessive wheel slippage occurs then Cye can become lost (possibly without realizing that it is lost). Thus Cye is suitable for use only in relatively small benign environments. Other examples of this approach are disclosed it U.S. Pat. No. 5,109,566 Kobayashi et al.) and U.S. Pat. No. 6,255,793 (Peless et al.).
Another approach to robotic cleaning is purely random motion. As shown in FIG. 1C, in a typical room without obstacles, a random movement algorithm will provide acceptable coverage given significant cleaning time. Compared to a robot with a deterministic algorithm, a random cleaning robot must operate for a longer time to achieve acceptable coverage. To have high confidence that the random-motion robot has cleaned 98% of an obstacle-free room, the random motion robot must run approximately five times as long as a deterministic robot with the same cleaning mechanism, moving at the same speed.
The coverage limitations of a random algorithm can be seen in FIG. 1D. An obstacle 5 in the room can create the effect of segmenting the room into a collection of chambers. The coverage over time of a random algorithm robot in such a room is analogous to the time density of gas released in one chamber of a confined volume. Initially, the density of gas is highest in the chamber where it is released and lowest in more distant chambers. Similarly the robot is most likely to thoroughly clean the chamber where it starts, rather than more distant chambers, early in the process. Given enough time a gas reaches equilibrium with equal density in all chambers. Likewise given time, the robot would clean all areas thoroughly. The limitations of practical power supplies, however, usually guarantee that the robot will have insufficient time to clean all areas of a space cluttered with obstacles. We refer to this phenomenon as the robot diffusion problem.
As discussed, the commercially available prior art has not been able to produce an effective coverage algorithm for an area of unknown geometry. As noted above, the prior art either has relied on sophisticated systems of markers or beacons or has limited the utility of the robot to rooms with simple rectangular geometries. Attempts to use pseudo-deterministic control algorithms can leave areas of the space systematically neglected.